class Solution {//leetcode446——等差数列划分II
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        unordered_map<long long,vector<int>> hash;
        hash[nums[0]].push_back(0);
        int ret=0;
        for(int j=1;j<n-1;j++){
            for(int i=j+1;i<n;i++){
                long long x=(long long)2*nums[j]-nums[i];
                if(hash.count(x)){
                    for(int k:hash[x])
                    {
                        dp[j][i]+=dp[k][j]+1;
                    }
                }
            }
            hash[nums[j]].push_back(j);
        }
        for(auto &lis:dp){
            for(auto e :lis){
                ret+=e;
            }
        }
        return ret;
    }
};